Internet Info 1993

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / inet / rfc / rfc956 < prev next >

Wrap

Text File | 1991-04-20 | 65.8 KB | 1,482 lines

Network Working Group D.L. Mills Request for Comments: 956 M/A-COM Linkabit September 1985 Algorithms for Synchronizing Network Clocks Status of this Memo This RFC discussed clock synchronization algorithms for the ARPA-Internet community, and requests discussion and suggestions for improvements. Distribution of this memo is unlimited. Table of Contents 1. Introduction 2. Majority-Subset Algorithms 3. Clustering Algorithms 4. Application to Time-Synchronization Data 5. Summary and Conclusions 6. References Appendix A. Experimental Determination of Internet Host Clock Accuracies A1. UDP Time Protocol Experiment A2. ICMP Timestamp Message Experiment A3. Comparison of UDP and ICMP Time List of Tables Table 1. C(n,k) for n from 2 to 20 Table 2. Majority Subsets for n = 3,4,5 Table 3. Clustering Algorithm using UDP Time Protocol Data Table 4. Clustering Algorithm using ICMP Timestamp Data Table 5. ISI-MCON-GW Majority-Subset Algorithm Table 6. ISI-MCON-GW Clustering Algorithm Table 7. LL-GW (a) Majority-Subset Algorithm Table 8. LL-GW (a) Clustering Algorithm Table 9. LL-GW (b) Majority-Subset Algorithm Table 10. LL-GW (b) Clustering Algorithm Table A1. UDP Host Clock Offsets for Various Internet Hosts Table A2. UDP Offset Distribution < 9 sec Table A3. UDP Offset Distribution < 270 sec Table A4. ICMP Offset Distribution < 9 hours Table A5. ICMP Offset Distribution < 270 sec Table A6. ICMP Offset Distribution < 27 sec Table A7. ICMP Offset Distribution < .9 sec Table A8. Comparison of UDP and ICMP Host Clock Offsets Mills [Page 1] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks 1. Introduction The recent interest within the Internet community in determining accurate time from a set of mutually suspicious network clocks has been prompted by several occasions in which gross errors were found in usually reliable, highly accurate clock servers after seasonal thunderstorms which disrupted their primary power supply. To these sources of error should be added those due to malfunctioning hardware, defective software and operator mistakes, as well as random errors in the mechanism used to set and/or synchronize the clocks via Internet paths. The results of these errors can range from simple disorientation to major disruption, depending upon the operating system, when files or messages are incorrectly timestamped or the order of critical network transactions is altered. This report suggests a stochastic model based on the principles of maximum-likelihood estimation, together with algorithms for computing a good estimator from a number of time-offset samples measured between one or more clocks connected via network links. The model provides a rational method for detecting and resolving errors due to faulty clocks or excessively noisy links. Included in this report are descriptions of certain experiments conducted with Internet hosts and ARPANET paths which give an indication of the effectiveness of the algorithms. Several mechanisms have been specified in the Internet protocol suite to record and transmit the time at which an event takes place, including the ICMP Timestamp message [6], Time Protocol [7], Daytime protocol [8] and IP Timestamp option [9]. A new Network Time Protocol [12] has been proposed as well. Additional information on network time synchronization can be found in the References at the end of this document. Synchronization protocols are described in [3] and [12] and synchronization algorithms in [2], [5] and [10]. Experimental results on measured roundtrip delays and clock offsets in the Internet are discussed in [4] and [11]. A comprehensive mathematical treatment of clock synchronization can be found in [1]. In [10] the problem of synchronizing a set of mutually suspicious clocks is discussed and algorithms offered which maximize in some sense the expectation that a correct set of "good" clocks can be extracted from the population including also "bad" ones. The technique is based upon overlapping, discrete confidence intervals which are assigned a-priori. The model assumes the reasonable presumption that "bad" clocks display errors far outside these confidence intervals, so can be easily identified and discarded from the voting process. Mills [Page 2] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks As apparent from the data summarized in Appendix A, host clocks in a real network commonly indicate various degrees of dispersion with respect to each other and to a standard-time reference such as a radio clock. The sources of dispersion include random errors due to observational phenomena and the synchronization mechanism itself, if used, as well as systematic errors due to hardware or software failure, poor radio reception conditions or operator mistakes. In general, it is not possible to accurately quantify whether the dispersion of any particular clock qualifies the clock as "good" or "bad," except on a statistical basis. Thus, from a practical standpoint, a statistical-estimation approach to the problem is preferred over a discrete-decision one. A basic assumption in this report is that the majority of "good" clocks display errors clustered around a zero offset relative to standard time, as determined for example from a radio clock, while the remaining "bad" clocks display errors distributed randomly over the observing interval. The problem is to select the good clocks from the bad and to estimate the correction to apply to the local clock in order to display the most accurate time. The algorithms described in this report attempt to do this using maximum-likelihood techniques, which are theory. It should be noted that the algorithms discussed in [10] and in this report are are basically filtering and smoothing algorithms and can result in errors, sometimes gross ones, if the sample distribution departs far from a-priori assumptions. Thus, a significant issue in the design of these algorithms is robustness in the face of skewed sample data sets. The approach in [10] uses theorem-proving to justify the robustness of the discrete algorithms presented; however, the statistical models in this report are not suited for that. The approach taken in this report is based on detailed observation and experiments, a summary of which is included as an appendix. While this gives an excellent qualitative foundation upon which to judge robustness, additional quantitative confidence should be developed through the use of statistical mechanics. 2. Majority-Subset Algorithms A stochastic model appropriate to a system of mutually suspicious clocks can be constructed as follows. An experiment consists of one or more measurements of time differences or offsets between several clocks in the network. Usually, but not necessarily, one of the clocks is the local clock at the observer and observations are conducted with each of several other clocks in the network. The fact that some clocks are presumed more accurate or trusted more highly than others can be expressed by weighting the measurements Mills [Page 3] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks accordingly. The result is a set of statistics, including means and variances, from which the observer is able to estimate the best time at which to set the local clock. A maximum-likelihood estimator is a statistic that maximizes the probability that a particular outcome of an experiment is due to a presumed set of assumptions on the constraints of the experiment. For example, if it is assumed that at least k of n observations include only samples from a single distribution, then a maximum-likelihood estimator for the mean of that distribution might be computed as follows: Determine the variance for every k-sample subset of the n observations. Then select the subset with smallest variance and use its mean as the estimator for the distribution mean. For instance, let n be the number of clocks and k be the next largest integer in n/2, that is, the minimum majority. A majority subset is a subset consisting of k of the n offset measurements. Each of these subsets can be represented by a selection of k out of n possibilities, with the total number of subsets equal to C(n,k). The number of majority subsets is tallied for n from 2 to 20 in Table 1. (n,k) C(n,k) (n,k) C(n,k) ---------------------- ---------------------- (2,2) 1 (11,6) 462 (3,2) 3 (12,7) 792 (4,3) 4 (13,7) 1716 (5,3) 10 (14,8) 3003 (6,4) 15 (15,8) 6435 (7,4) 35 (16,9) 11440 (8,5) 56 (17,9) 24310 (9,5) 126 (18,10) 43758 (10,6) 210 (19,10) 92378 (20,11) 167960 Table 1. C(n,k) for n from 2 to 20 Obviously, the number of computations required becomes awkward as n increases beyond about 10. Representative majority subsets for n = 3,4,5 are shown in Table 2. Mills [Page 4] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks C(3,2) C(4,3) C(5,3) ------ ------ ------ 1,2 1,2,3 1,2,3 1,3 1,2,4 1,2,4 2,3 1,3,4 1,2,5 2,3,4 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 Table 2. Majority Subsets for n = 3,4,5 Choosing n = 5, for example, requires calculation of the mean and variance for ten subsets indexed as shown in Table 2. A maximum-likelihood algorithm with provision for multiple samples and weights might operate as follows: Let n be the number of clocks and w(1),w(2),...,w(n) a set of integer weights, with w(i) the weight associated with the ith clock. For the ith clock three accumulators W(i), X(i) and Y(i) are provided, each initialized to zero. The ith clock is polled some number of times, with each reply x causing n(i) to be added to W(i), as well as the weighted sample offset n(i)*x added to X(i) and its square (n(i)*x)2 added to Y(i). Polling is continued for each of the n clocks in turn. Next, using a majority-subset table such as shown in Table 2, calculate the total weight W = sum(W(i)) and weighted sums X = sum(X(i)) and Y = sum(Y(i)*Y(i)) for each i in the jth majority subset (row). From W, X and Y calculate the mean m(j) and variance s(j): m(j) = X/W and s(j) = Y/W - m(j)*m(j) . When this is complete for all rows, select the row j with the smallest s(j) and return the associated mean m(j) as the maximum-likelihood estimate of the local-clock offset. Mills [Page 5] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks 3. Clustering Algorithms Another method for developing a maximum-likelihood estimator is through the use of clustering algorithms. These algorithms operate to associate points in a sample set with clusters on the basis of stochastic properties and are most useful when large numbers of samples are available. One such algorithm operates on a sample set to selectively discard points presumed outside the cluster as follows: 1. Start with a sample set of n observations {x(1),x(2),...,x(n) 2. Compute the mean of the n observations in the sample set. Discard the single sample x(i) with value furthest from the mean, leaving n-1 observations in the set. 3. Continue with step 2 until only a single observation is left, at which point declare its value the maximum-likelihood estimator. This algorithm will usually (but not necessarily) converge to the desired result if the majority of observations are the result of "good" clocks, which by hypothesis are clustered about zero offset relative to the reference clock, with the remainder scattered randomly over the observation interval. The following Table 3 summarizes the results of this algorithm applied to the UDP data shown in Appendix A, which represents the measured clock offsets of 163 host clocks in the Internet system. These data were assembled using the UDP Time protocol [7], in which time is represented to a precision of one second. Each line of the table represents the result of step 2 above along with the size of the sample set and its (unweighted) mean and variance. The "Discard" column shows the value of the observation discarded at that step. Mills [Page 6] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks Size Mean Var Discard ------------------------------- 163 -210 9.1E+6 -38486 162 26 172289 3728 161 3 87727 3658 160 -20 4280 -566 150 -17 1272 88 100 -18 247 -44 50 -4 35 8 20 -1 0 -2 19 -1 0 -2 18 -1 0 -2 17 -1 0 1 16 -1 0 -1 15 -1 0 -1 14 -1 0 -1 13 0 0 0 1 0 0 0 Table 3. Clustering Algorithm using UDP Time Protocol Data In Table 3 only a few of the 163 steps are shown, including those near the beginning which illustrate a rapid convergence as the relatively few outliers are discarded. The large outlier discarded in the first step is almost certainly due to equipment or operator failure. The two outliers close to one hour discarded in the next two steps are probably simple operator mistakes like entering summer time instead of standard time. By the time only 50 samples are left, the error has shrunk to about 4 sec and the largest outlier is within 12 sec of the estimate. By the time only 20 samples are left, the error has shrunk to about a second and the variance has vanished for practical purposes. The following Table 4 summarizes the results of the clustering algorithm applied to the ICMP data shown in Appendix A, which represents the measured clock offsets of 504 host clocks in the Internet system. These data were assembled using ICMP Timestamp messages [6], in which time is represented to a precision of one millisecond. The columns in Table 4 should be interpreted in the same way as in Table 3, except that the data in Table 4 are in milliseconds, while the data in Table 3 are in seconds. Mills [Page 7] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks Size Mean Var Discard ------------------------------- 504 -3.0E+6 3.2E+14 8.6E+7 500 -3.3E+6 2.9E+14 8.6E+7 450 -1.6E+6 3.0E+13 -2.5E+7 400 29450 2.2E+11 3.6E+6 350 -3291 4.1E+9 -185934 300 3611 1.6E+9 -95445 250 2967 6.8E+8 66743 200 4047 2.3E+8 39288 150 1717 8.6E+7 21346 100 803 1.9E+7 10518 80 1123 8.4E+6 -4863 60 1119 3.1E+6 4677 50 502 1.5E+6 -2222 40 432 728856 2152 30 84 204651 -987 20 30 12810 338 15 28 2446 122 10 7 454 49 8 -2 196 24 6 -9 23 0 4 -10 5 -13 2 -8 0 -8 Table 4. Clustering Algorithm using ICMP Timestamp Data As in Table 3 above, only some of the 504 steps are shown in Table 4. The distinguishing feature of the data in Table 4 is that the raw data are much more noisy - only some 30 host clocks are closer than one second from the reference clock, while half were further than one minute and over 100 further than one hour from it. The fact that the algorithm converged to within 8 msec of the reference time under these conditions should be considered fairly remarkable in view of the probability that many of the outliers discarded are almost certainly due to defective protocol implementations. Additional information on these experiments is presented in Appendix A. Mills [Page 8] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks 4. Application to Time-Synchronization Data A variation of the above algorithms can be used to improve the offset estimates from a single clock by discarding noise samples produced by occasional retransmissions in the network, for example. A set of n independent samples is obtained by polling the clock. Then, a majority-subset table is used to compute the m(j) and s(j) statistics and the maximum-likelihood estimate determined as above. For this purpose the majority-subset table could include larger subsets as well. In this manner the maximum-likelihood estimates from each of several clocks can be determined and used in the algorithm above. In order to test the effectiveness of this algorithm, a set of experiments was performed using two WIDEBAND/EISN gateways equipped with WWVB radio clocks and connected to the ARPANET. These experiments were designed to determine the limits of accuracy when comparing these clocks via ARPANET paths. One of the gateways (ISI-MCON-GW) is located at the Information Sciences Institute near Los Angeles, while the other (LL-GW) is located at Lincoln Laboratories near Boston. Both gateways consist of PDP11/44 computers running the EPOS operating system and clock-interface boards with oscillators phase-locked to the WWVB clock. The clock indications of the WIDEBAND/EISN gateways were compared with the DCNet WWVB reference clock using ICMP Timestamp messages, which record the individual timestamps with a precision of a millisecond. However, the path over the ARPANET between these gateways and the measurement host can introduce occasional measurement errors as large as several seconds. In principle the effect of these errors can be minimized by using a large sample population; however, use of the above algorithms allows higher accuracies to be obtained with far fewer samples. Measurements were made separately with each of the two gateways by sending an ICMP Timestamp Request message from the ARPANET address of DCN1 to the ARPANET address of the gateway and computing the round-trip delay and clock offset from the ICMP Timestamp Reply message. This process was continued for 1000 message exchanges, which took from seven minutes to several hours, depending on the sample interval selected. The tables below summarize the results of both the majority-subset and clustering algorithms applied to the data from three experiments, one with ISI-MCON-GW and two with LL-GW. The ISI-MCON-GW and LL-GW (a) experiments were designed to determine the limits of accuracy when using a continuous sequence of request/reply volleys, which Mills [Page 9] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks resulted in over two samples per second. The remaining LL-GW (b) experiment was designed to determine the limits of accuracy using a much lower rate of about one sample every ten seconds. For each of the three experiments two tables are shown, one using the majority-subset algorithm and the other the clustering algorithm. The two rows of the majority-subset tables show the statistics derived both from the raw data and from the filtered data processed by a C(5,3) majority-subset algorithm. In all cases the extrema and variance are dramatically less for the filtered data than the raw data, lending credence to the conjecture that the mean statistic for the filtered data is probably a good maximum-likelihood estimator of the true offset. Mean Var Max Min -------------------------------------------- Raw data 637 2.1E+7 32751 -1096 C(5,3) -15 389 53 -103 Table 5. ISI-MCON-GW Majority-Subset Algorithm Size Mean Var Discard ------------------------------- 1000 637 2.1E+7 32751 990 313 1.0E+7 32732 981 15 1.0E+6 32649 980 -18 2713 -1096 970 -15 521 -122 960 -15 433 -97 940 -15 332 -75 900 -15 239 26 800 -15 141 12 700 -16 87 5 600 -17 54 -31 500 -16 33 -5 400 -18 18 -9 300 -19 7 -12 200 -19 2 -21 100 -18 0 -19 1 -17 0 -17 Table 6. ISI-MCON-GW Clustering Algorithm Mills [Page 10] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks Mean Dev Max Min -------------------------------------------- Raw data 566 1.8E+7 32750 -143 C(5,3) -23 81 14 -69 Table 7. LL-GW (a) Majority-Subset Algorithm Size Mean Var Discard ------------------------------- 1000 566 1.8E+7 32750 990 242 8.5E+6 32726 983 10 1.0E+6 32722 982 -23 231 -143 980 -23 205 -109 970 -22 162 29 960 -23 128 13 940 -23 105 -51 900 -24 89 1 800 -25 49 -9 700 -26 31 -36 600 -26 21 -34 500 -27 14 -20 400 -29 7 -23 300 -30 3 -33 200 -29 1 -27 100 -29 0 -28 1 -29 0 -29 Table 8. LL-GW (a) Clustering Algorithm Mean Dev Max Min -------------------------------------------- Raw data 378 2.1E+7 32760 -32758 C(5,3) -21 1681 329 -212 Table 9. LL-GW (b) Majority-Subset Algorithm Mills [Page 11] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks Size Mean Var Discard ------------------------------- 1000 377 2.1E+7 -32758 990 315 1.0E+7 32741 981 18 1.1E+6 32704 980 -16 16119 -1392 970 -17 5382 554 960 -21 3338 311 940 -24 2012 168 900 -22 1027 -137 800 -23 430 -72 700 -23 255 -55 600 -22 167 -45 500 -22 109 -40 400 -21 66 -6 300 -18 35 -29 200 -17 15 -23 100 -19 3 -15 50 -21 0 -19 20 -21 0 -21 10 -20 0 -20 1 -20 0 -20 Table 10. LL-GW (b) Clustering Algorithm The rows of the clustering tables show the result of selected steps in the algorithm as it discards samples furthest from the mean. The first twenty steps or so discard samples with gross errors over 30 seconds. These samples turned out to be due to a defect in the timestamping procedure implemented in the WIDEBAND/EISN gateway code which caused gross errors in about two percent of the ICMP Timestamp Reply messages. These samples were left in the raw data as received in order to determine how the algorithms would behave in such extreme cases. As apparent from the tables, both the majority-subset and clustering algorithms effectively coped with the situation. In the statement of the clustering algorithm the terminating condition was specified as when only a single sample is left in the sample set. However, it is not necessary to proceed that far. For instance, it is known from the design of the experiment and the reference clocks that accuracies better than about ten milliseconds are probably unrealistic. A rough idea of the accuracy of the mean is evident from the deviation, computed as the square root of the variance. Thus, attempts to continue the algorithm beyond the point where the variance drops below 100 or so are probably misguided. This occurs when between 500 and 900 samples remain in the sample Mills [Page 12] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks set, depending upon the particular experiment. Note that in any case between 300 and 700 samples fall within ten milliseconds of the final estimate, depending on experiment. Comparing the majority-subset and clustering algorithms on the basis of variance reveals the interesting observation that the result of the C(5,3) majority-subset algorithm is equivalent to the clustering algorithm when between roughly 900 and 950 samples remain in the sample set. This together with the moderately high variance in the ISI-MCON-GW and LL-GW (b) cases suggests a C(6,4) or even C(7,4) algorithm might yield greater accuracies. 5. Summary and Conclusions The principles of maximum-likelihood estimation are well known and widely applied in communication electronics. In this note two algorithms using these principles are proposed, one based on majority-subset techniques appropriate for cases involving small numbers of samples and the other based on clustering techniques appropriate for cases involving large numbers of samples. The algorithms were tested on raw data collected with Internet hosts and gateways over ARPANET paths for the purpose of setting a local host clock with respect to a remote reference while maintaining accuracies in the order of ten milliseconds. The results demonstrate the effectiveness of these algorithms in detecting and discarding glitches due to hardware or software failure or operator mistakes. They also demonstrate that time synchronization can be maintained across the ARPANET in the order of ten milliseconds in spite of glitches many times the mean roundtrip delay. The results point to the need for an improved time-synchronization protocol combining the best features of the ICMP Timestamp message [6] and UDP Time protocol [7]. Among the features suggested for this protocol are the following: 1. The protocol should be based on UDP, which provides the flexibility to handle simultaneous, multiplexed queries and responses. 2. The message format should be based on the ICMP Timestamp message format, which provides the arrival and departure times at the server and allows the client to calculate the roundtrip delay and offset accurately. Mills [Page 13] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks 3. The data format should be based on the UDP Time format, which specifies 32-bit time in seconds since 1 January 1900, but extended additional bits for the fractional part of a second. 4. Provisions to specify the expected accuracy should be included along with information about the reference clock or synchronizing mechanism, as well as the expected drift rate and the last time the clock was set or synchronized. The next step should be formulating an appropriate protocol with the above features, together with implementation and test in the Internet environment. Future development should result in a distributed, symmetric protocol, similar perhaps to those described in [1], for distributing highly reliable timekeeping information using a hierarchical set of trusted clocks. 6. References 1. Lindsay, W.C., and A.V. Kantak. Network synchronization of random signals. IEEE Trans. Comm. COM-28, 8 (August 1980), 1260-1266. 2. Mills, D.L. Time Synchronization in DCNET Hosts. DARPA Internet Project Report IEN-173, COMSAT Laboratories, February 1981. 3. Mills, D.L. DCNET Internet Clock Service. DARPA Network Working Group Report RFC-778, COMSAT Laboratories, April 1981. 4. Mills, D.L. Internet Delay Experiments. DARPA Network Working Group Report RFC-889, M/A-COM Linkabit, December 1983. 5. Mills, D.L. DCN Local-Network Protocols. DARPA Network Working Group Report RFC-891, M/A-COM Linkabit, December 1983. 6. Postel, J. Internet Control Message Protocol. DARPA Network Working Group Report RFC-792, USC Information Sciences Institute, September 1981. 7. Postel, J. Time Protocol. DARPA Network Working Group Report RFC-868, USC Information Sciences Institute, May 1983. 8. Postel, J. Daytime Protocol. DARPA Network Working Group Report RFC-867, USC Information Sciences Institute, May 1983. 9. Su, Z. A Specification of the Internet Protocol (IP) Timestamp Option. DARPA Network Working Group Report RFC-781. SRI International, May 1981. Mills [Page 14] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks 10. Marzullo, K., and S. Owicki. Maintaining the Time in a Distributed System. ACM Operating Systems Review 19, 3 (July 1985), 44-54. 11. Mills, D.L. Experiments in Network Clock Synchronization. DARPA Network Working Group Report RFC-957, M/A-COM Linkabit, September 1985. 12. Mills, D.L. Network Time Protocol (NTP). DARPA Network Working Group Report RFC-958, M/A-COM Linkabit, September 1985. Appendix A. Experimental Determination of Internet Host Clock Accuracies Following is a summary of the results of three experiments designed to reveal the accuracies of various Internet host clocks. The first experiment uses the UDP Time protocol, which is limited in precision to one second, while the second uses the ICMP Timestamp message, which extends the precision to one millisecond. In the third experiment the results indicated by UDP and ICMP are compared. In the UDP Time protocol time is indicated as a 32-bit field in seconds past 0000 UT on 1 January 1900, while in the ICMP Timestamp message time is indicated as a 32-bit field in milliseconds past 0000 UT of each day. All experiments described herein were conducted from Internet host DCN6.ARPA, which is normally synchronized to a WWV radio clock. In order to improve accuracy during the experiments, the DCN6.ARPA host was resynchronized to a WWVB radio clock. As the result of several experiments with other hosts equipped with WWVB and WWV radio clocks and GOES satellite clocks, it is estimated that the maximum measurement error in the following experiments is less than about 30 msec relative to standard NBS time determined at the Boulder/Fort Collins transmitting sites. A1. UDP Time Protocol Experiment In the first experiment four UDP Time protocol requests were sent at about three-second intervals to each of the 1775 hosts listed in the NIC Internet host table. A total of 555 samples were received from 163 hosts and compared with a local reference based on a WWVB radio clock, which is known to be accurate to within a few milliseconds. Not all of these hosts were listed as supporting the UDP Time protocol in the NIC Internet host table, while some that were listed as supporting this protocol either failed to respond or responded with various error messages. Mills [Page 15] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks In the following table "Host" is the canonical name of the host and "Count" the number of replies received. The remaining data represent the time offset, in seconds, necessary to correct the local (reference) clock to agree with the host cited. The "Max" and "Min" represent the maximum and minimum of these offsets, while "Mean" represents the mean value and "Var" the variance, all rounded to the nearest second. Host Count Max Min Mean Var ----------------------------------------------------------- BBN-CLXX.ARPA 4 -11 -12 -11 0 BBN-KIWI.ARPA 4 -11 -12 -11 0 BBN-META.ARPA 4 -11 -12 -11 0 BBNA.ARPA 1 22 22 22 0 BBNG.ARPA 4 87 87 87 0 BELLCORE-CS-GW.ARPA 3 72 71 71 0 BLAYS.PURDUE.EDU 2 -1 -1 -1 0 CMU-CC-TE.ARPA 4 -94 -95 -94 0 CMU-CS-C.ARPA 3 6 5 5 0 CMU-CS-CAD.ARPA 4 -37 -37 -37 0 CMU-CS-CFS.ARPA 3 -42 -43 -42 0 CMU-CS-G.ARPA 3 -30 -31 -30 0 CMU-CS-GANDALF.ARPA 3 -42 -43 -42 0 CMU-CS-H.ARPA 4 -36 -37 -36 0 CMU-CS-IUS.ARPA 3 -44 -45 -44 0 CMU-CS-IUS2.ARPA 3 -44 -44 -44 0 CMU-CS-K.ARPA 3 -31 -31 -31 0 CMU-CS-SAM.ARPA 4 -74 -75 -74 0 CMU-CS-SPEECH.ARPA 4 -39 -40 -39 0 CMU-CS-SPEECH2.ARPA 4 -49 -50 -49 0 CMU-CS-SPICE.ARPA 4 -131 -132 -131 0 CMU-CS-THEORY.ARPA 4 -36 -37 -36 0 CMU-CS-UNH.ARPA 4 -44 -45 -44 0 CMU-CS-VLSI.ARPA 4 -66 -66 -66 0 CMU-RI-ARM.ARPA 3 -41 -41 -41 0 CMU-RI-CIVE.ARPA 3 -44 -45 -44 0 CMU-RI-FAS.ARPA 4 -27 -28 -27 0 CMU-RI-ISL1.ARPA 4 -18 -19 -18 0 CMU-RI-ISL3.ARPA 3 -49 -50 -49 0 CMU-RI-LEG.ARPA 3 -33 -33 -33 0 CMU-RI-ML.ARPA 4 42 42 42 0 CMU-RI-ROVER.ARPA 4 -48 -49 -48 0 CMU-RI-SENSOR.ARPA 2 -40 -41 -40 0 CMU-RI-VI.ARPA 3 -65 -65 -65 0 COLUMBIA.ARPA 1 8 8 8 0 CU-ARPA.CS.CORNELL.EDU 4 5 3 4 0 CYPRESS.ARPA 4 2 1 1 0 Mills [Page 16] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks DCN1.ARPA 4 0 0 0 0 DCN5.ARPA 4 0 0 0 0 DCN6.ARPA 4 0 0 0 0 DCN7.ARPA 4 -1 -1 0 0 DCN9.ARPA 4 -3 -3 -3 0 DEVVAX.TN.CORNELL.EDU 2 3659 3658 3658 0 ENEEVAX.ARPA 4 73 72 72 0 FORD-WDL1.ARPA 4 -59 -60 -59 0 FORD1.ARPA 4 0 0 0 0 GUENEVERE.PURDUE.EDU 3 1 0 0 0 GVAX.CS.CORNELL.EDU 4 -18 -18 -18 0 IM4U.ARPA 4 -6 -6 -6 0 IPTO-FAX.ARPA 4 0 0 0 0 KANKIN.ARPA 4 -3 -4 -3 0 MERLIN.PURDUE.EDU 2 3 3 3 0 MIT-ACHILLES.ARPA 4 16 16 16 0 MIT-AGAMEMNON.ARPA 4 -63 -64 -63 0 MIT-ANDROMACHE.ARPA 4 -28 -28 -28 0 MIT-APHRODITE.ARPA 4 -7 -8 -7 0 MIT-APOLLO.ARPA 4 -8 -9 -8 0 MIT-ARES.ARPA 4 -25 -26 -25 0 MIT-ARTEMIS.ARPA 4 -34 -35 -34 0 MIT-ATHENA.ARPA 4 -37 -37 -37 0 MIT-ATLAS.ARPA 4 -26 -26 -26 0 MIT-CASTOR.ARPA 4 -35 -35 -35 0 MIT-DAFFY-DUCK.ARPA 2 -72 -73 -72 0 MIT-DEMETER.ARPA 4 -28 -29 -28 0 MIT-GOLDILOCKS.ARPA 1 -20 -20 -20 0 MIT-HECTOR.ARPA 4 -23 -24 -23 0 MIT-HELEN.ARPA 4 6 5 5 0 MIT-HERA.ARPA 4 -34 -35 -34 0 MIT-HERACLES.ARPA 4 -36 -36 -36 0 MIT-JASON.ARPA 4 -36 -37 -36 0 MIT-MENELAUS.ARPA 4 -32 -33 -32 0 MIT-MULTICS.ARPA 3 25 23 24 0 MIT-ODYSSEUS.ARPA 4 20 19 19 0 MIT-ORPHEUS.ARPA 4 -34 -35 -34 0 MIT-PARIS.ARPA 4 -35 -35 -35 0 MIT-POSEIDON.ARPA 4 -39 -41 -40 0 MIT-PRIAM.ARPA 4 -24 -25 -24 0 MIT-REAGAN.ARPA 4 115 115 115 0 MIT-THESEUS.ARPA 4 -43 -44 -43 0 MIT-TRILLIAN.ARPA 4 -38 -39 -38 0 MIT-TWEETY-PIE.ARPA 3 106 105 105 0 MIT-ZERMATT.ARPA 4 -75 -76 -75 0 MIT-ZEUS.ARPA 4 -37 -39 -38 0 MOL.ARPA 2 -3 -3 -3 0 Mills [Page 17] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks MUNGO.THINK.COM 4 -1 -1 -1 0 NETWOLF.ARPA 4 158 157 157 0 ORBIT.ARPA 3 -4 -5 -4 0 OSLO-VAX.ARPA 3 3729 3727 3728 1 PATCH.ARPA 1 18 18 18 0 RADC-MULTICS.ARPA 4 -14 -15 -14 0 RICE-ZETA.ARPA 1 -31 -31 -31 0 RICE.ARPA 1 7 7 7 0 ROCHESTER.ARPA 4 -18 -18 -18 0 ROCK.THINK.COM 4 2 2 2 0 SCRC-QUABBIN.ARPA 4 -100 -100 -100 0 SCRC-RIVERSIDE.ARPA 4 -128 -128 -128 0 SCRC-STONY-BROOK.ARPA 4 -100 -100 -100 0 SCRC-VALLECITO.ARPA 4 -57 -57 -57 0 SCRC-YUKON.ARPA 4 -65 -65 -65 0 SEBASTIAN.THINK.COM 4 -14 -15 -14 0 SEISMO.CSS.GOV 3 -1 -1 0 0 SRI-BISHOP.ARPA 4 -40 -41 -40 0 SRI-DARWIN.ARPA 2 -29 -30 -29 0 SRI-HUXLEY.ARPA 2 -28 -29 -28 0 SRI-KIOWA.ARPA 4 -29 -30 -29 0 SRI-LASSEN.ARPA 3 -11 -12 -11 0 SRI-MENDEL.ARPA 4 74 73 73 0 SRI-PINCUSHION.ARPA 4 -50 -51 -50 0 SRI-RITTER.ARPA 4 -23 -24 -23 0 SRI-TIOGA.ARPA 4 127 127 127 0 SRI-UNICORN.ARPA 4 -38486 -38486 -38486 0 SRI-WHITNEY.ARPA 4 -24 -24 -24 0 SRI-YOSEMITE.ARPA 4 -26 -27 -26 0 SU-AIMVAX.ARPA 2 -54 -55 -54 0 SU-COYOTE.ARPA 1 14 14 14 0 SU-CSLI.ARPA 4 -1 -1 -1 0 SU-PSYCH.ARPA 1 -52 -52 -52 0 SU-SAFE.ARPA 1 -60 -60 -60 0 SU-SIERRA.ARPA 4 -53 -53 -53 0 SU-SUSHI.ARPA 4 -105 -106 -105 0 SU-WHITNEY.ARPA 2 -14 -14 -14 0 TESLA.EE.CORNELL.EDU 3 -2 -3 -2 0 THORLAC.THINK.COM 4 -20 -20 -20 0 TRANTOR.ARPA 4 4 3 3 0 TZEC.ARPA 4 -6 -7 -6 0 UBALDO.THINK.COM 4 -13 -13 -13 0 UCI-CIP.ARPA 2 -566 -567 -566 0 UCI-CIP2.ARPA 2 -175 -175 -175 0 UCI-CIP3.ARPA 2 -89 -90 -89 0 UCI-CIP4.ARPA 2 -51 -51 -51 0 UCI-CIP5.ARPA 2 -26 -28 -27 1 Mills [Page 18] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks UCI-ICSA.ARPA 2 -24 -24 -24 0 UCI-ICSC.ARPA 1 0 0 0 0 UCI-ICSD.ARPA 1 -24 -24 -24 0 UCI-ICSE.ARPA 1 -10 -10 -10 0 UDEL-DEWEY.ARPA 1 88 88 88 0 UDEL-MICRO.ARPA 2 64 64 64 0 UIUC.ARPA 4 105 103 104 0 UIUCDCSB.ARPA 4 65 65 65 0 UMD1.ARPA 4 0 0 0 0 UMICH1.ARPA 4 -1 -1 0 0 UO.ARPA 4 -2 -3 -2 0 USC-ISI.ARPA 4 -45 -45 -45 0 USC-ISIC.ARPA 4 28 26 27 0 USC-ISID.ARPA 4 26 25 25 0 USC-ISIE.ARPA 4 -53 -54 -53 0 USC-ISIF.ARPA 4 -29 -29 -29 0 USGS2-MULTICS.ARPA 3 75 74 74 0 UT-ALAMO.ARPA 4 22 22 22 0 UT-BARKLEY.ARPA 4 57 56 56 0 UT-EMIL.ARPA 4 29 28 28 0 UT-GOTTLOB.ARPA 4 42 41 41 0 UT-HASKELL.ARPA 4 6 6 6 0 UT-JACQUES.ARPA 4 21 20 20 0 UT-SALLY.ARPA 3 1 0 0 0 VALENTINE.THINK.COM 4 -10 -11 -10 0 WENCESLAS.THINK.COM 4 -2 -3 -2 0 XAVIER.THINK.COM 4 -14 -14 -14 0 XEROX.ARPA 4 0 0 0 0 YAXKIN.ARPA 3 -4 -5 -4 0 YON.THINK.COM 4 -11 -12 -11 0 ZAPHOD.PURDUE.EDU 4 -230 -231 -230 0 ZOTZ.ARPA 4 17 16 16 0 Table A1. UDP Host Clock Offsets for Various Internet Hosts The above list includes several host clocks known to be synchronized to various radio clocks, including DCN1.ARPA (WWVB), DCN6.ARPA (WWV) and FORD1.ARPA (GOES). Under normal radio receiving conditions these hosts should be accurate to well within a second relative to NBS standard time. Certain other host clocks are synchronized to one of these hosts using protocols described in RFC-891, including DCN5.ARPA, DCN7.ARPA and UMD1.ARPA (synchronized to DCN1.ARPA) and UMICH1.ARPA (synchronized to FORD1.ARPA). It is highly likely, but not confirmed, that several other hosts with low offsets derive local time from one of these hosts or from other radio clocks. Mills [Page 19] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks The raw statistics computed from the weighted data indicate a mean of -261 sec, together with a maximum of 3729 sec and a minimum of -38486 sec. Obviously, setting a local clock on the basis of these statistics alone would result in a gross error. A closer look at the distribution of the data reveals some interesting features. Table A2 is a histogram showing the distribution within a few seconds of reference time. In this and following tables, "Offset" is in seconds and indicates the lower-valued corner of the histogram bin, which extends to the next higher value, while "Count" indicates the number of samples falling in that bin. Offset Count Offset Count ------------- ------------- 0 sec 13 (continued) 1 1 -1 3 2 1 -2 3 3 2 -3 3 4 1 -4 2 5 2 -5 0 6 1 -6 2 7 1 -7 1 8 1 -8 1 9 0 -9 0 > 9 30 < -9 95 Table A2. Offset Distribution < 9 sec A total of 16 of the 163 host clocks are within a second in accuracy, while a total of 125 are off more than ten seconds. It is considered highly likely that most of the 16 host clocks within a second in offset are synchronized directly or indirectly to a radio clock. Table A3 is a histogram showing the distribution over a larger scale. Mills [Page 20] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks Offset Count Offset Count ------------- ------------- 0 sec 35 (continued) 30 3 -30 50 60 8 -60 42 90 3 -90 8 120 1 -120 4 150 1 -150 2 180 0 -180 1 210 0 -210 0 240 0 -240 1 270 0 -270 0 > 270 2 < -270 2 Table A3. Offset Distribution < 270 sec A total of 138 of the 163 host clocks are within a minute in accuracy, while a total of four host clocks are off more than 4.5 minutes. It is considered likely that most host clocks, with the exception of the 16 identified above as probably synchronized to a radio clock, are set manually by an operator. Inspection of the raw data shows some hosts to be very far off; for instance, SRI-UNICORN.ARPA is off more than ten hours. Note the interesting skew in the data, which show that most host clocks are set slow relative to standard time. A2. ICMP Timestamp Messages Experiment The the second experiment four ICMP Timestamp messages were sent at about three-second intervals to each of the 1775 hosts and 110 gateways listed in the NIC Internet host table. A total of 1910 samples were received from 504 hosts and gateways and compared with a local reference based on a WWVB radio clock, which is known to be accurate to within a few milliseconds. Support for the ICMP Timestamp messages is optional in the DoD Internet protocol suite, so it is not surprising that most hosts and gateways do not support it. Moreover, bugs are known to exist in several widely distributed implementations of this feature. The situation proved an interesting and useful robustness test for the clustering algorithm described in the main body of this note. While the complete table of ICMP offsets by host is too large to reproduce here, the following Tables A4 through A7 show the interesting characteristics of the distribution. The raw statistics computed from the weighted data indicate a mean of -2.8E+6 msec, together with a maximum of 8.6E+7 msec and a minimum of -8.6E+7 msec. Setting a local clock on the basis of these Mills [Page 21] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks statistics alone would be ridiculous; however, as described in the main body of this note, use of the clustering algorithm improves the estimate to within 8 msec of the correct value. The apparent improvement of about six orders in magnitude is so remarkable as to require a closer look at the distributions. The reasons for the remarkable success of the clustering algorithm are apparent from closer examination of the sequence of histograms shown in Tables A4 through A7. Table A4 shows the distribution in the scale of hours, from which it is evident that 80 percent of the samples lie in a one-hour band either side of zero offset; but, strangely enough, there is a significant dispersion in samples outside of this band, especially in the negative region. It is almost certain that most or all of the latter samples represent defective ICMP Timestamp implementations. Note that invalid timestamps and those with the high-order bit set (indicating unknown or nonstandard time) have already been excluded from these data. Offset Count Offset Count ------------- ------------- 0 hr 204 (continued) 1 10 -1 194 2 0 -2 0 3 0 -3 2 4 0 -4 17 5 0 -5 10 6 0 -6 1 7 0 -7 22 8 0 -8 20 9 0 -9 0 > 9 0 < -9 13 Table A4. ICMP Offset Distribution < 9 hours Table A5 shows the distribution compressed to the range of 4.5 minutes. About half of the 370 samples remaining after the outliers beyond 4.5 minutes are excluded lie in the band 30 seconds either side of zero offset, with a gradual tapering off to the limits of the table. This type of distribution would be expected in the case of host clocks set manually by an operator. Mills [Page 22] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks Offset Count Offset Count ------------- ------------- 0 sec 111 (continued) 30 25 -30 80 60 26 -60 28 90 13 -90 18 120 7 -120 19 150 5 -150 9 180 3 -180 10 210 3 -210 6 240 1 -240 2 270 2 -270 2 > 270 29 < -270 105 Table A5. ICMP Offset Distribution < 270 sec Table A6 shows the distribution compressed to the range of 27 seconds. About 29 percent of the 188 samples remaining after the outliers beyond 27 seconds are excluded lie in the band 3 seconds either side of zero offset, with a gradual but less pronounced tapering off to the limits of the table. This type of distribution is consistent with a transition region in which some clocks are set manually and some by some kind of protocol interaction with a reference clock. A fair number of the clocks showing offsets in the 3-27 second range have probably been set using the UDP Time protocol at some time in the past, but have wandered away as the result of local-oscillator drifts. Offset Count Offset Count ------------- ------------- 0 sec 32 (continued) 3 15 -3 22 6 9 -6 12 9 6 -9 8 12 13 -12 8 15 5 -15 5 18 8 -18 9 21 8 -21 7 24 9 -24 3 27 6 -27 3 > 27 114 < -27 202 Table A6. ICMP Offset Distribution < 27 sec Finally, Table A7 shows the distribution compressed to the range of 0.9 second. Only 30 of the original 504 samples have survived and only 12 of these are within a band 0.1 seconds either side of Mills [Page 23] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks zero offset. The latter include those clocks continuously synchronized to a radio clock, such as the DCNet clocks, some FORDnet and UMDnet clocks and certain others. Offset Count Offset Count ------------- ------------- 0 sec 6 (continued) .1 3 -.1 6 .2 1 -.2 3 .3 1 -.3 0 .4 0 -.4 0 .5 1 -.5 2 .6 0 -.6 0 .7 1 -.7 0 .8 4 -.8 2 .9 0 -.9 0 > .9 208 < -.9 266 Table A7. ICMP Offset Distribution < .9 sec The most important observation that can be made about the above histograms is the pronounced central tendency in all of them, in spite of the scale varying over six orders of magnitude. Thus, a clustering algorithm which operates to discard outliers from the mean will reliably converge on a maximum-likelihood estimate close to the actual value. A3. Comparison of UDP and ICMP Time The third experiment was designed to assess the accuracies produced by the various host implementations of the UDP Time protocol and ICMP Timestamp messages. For each of the hosts responding to the UDP Time protocol in the first experiment a separate test was conducted using both UDP and ICMP in the same test, so as to minimize the effect of clock drift. Of the 162 hosts responding to UDP requests, 45 also responded to ICMP requests with apparently correct time, but the remainder either responded with unknown or nonstandard ICMP time (29) or failed to respond to ICMP requests at all (88). Table A8 shows both the UDP time (seconds) and ICMP time (milliseconds) returned by each of the 45 hosts responding to both UDP and ICMP requests. The data are ordered first by indicated UDP offset and then by indicated ICMP offset. The seven hosts at the top of the table are continuously synchronized, directly or indirectly to a radio clock, as described earlier under the first Mills [Page 24] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks experiment. It is probable, but not confirmed, that those hosts below showing discrepancies of a second or less are synchronized on occasion to one of these hosts. Host UDP time ICMP time ------------------------------------------------- DCN6.ARPA 0 sec 0 msec DCN7.ARPA 0 0 DCN1.ARPA 0 -6 DCN5.ARPA 0 -7 UMD1.ARPA 0 8 UMICH1.ARPA 0 -21 FORD1.ARPA 0 31 TESLA.EE.CORNELL.EDU 0 132 SEISMO.CSS.GOV 0 174 UT-SALLY.ARPA -1 -240 CU-ARPA.CS.CORNELL.EDU -1 -514 UCI-ICSE.ARPA -1 -1896 UCI-ICSC.ARPA 1 2000 DCN9.ARPA -7 -6610 TRANTOR.ARPA 10 10232 COLUMBIA.ARPA 11 12402 GVAX.CS.CORNELL.EDU -12 -11988 UCI-CIP5.ARPA -15 -17450 RADC-MULTICS.ARPA -16 -16600 SU-WHITNEY.ARPA 17 17480 UCI-ICSD.ARPA -20 -20045 SU-COYOTE.ARPA 21 21642 MIT-MULTICS.ARPA 27 28265 BBNA.ARPA -34 -34199 UCI-ICSA.ARPA -37 -36804 ROCHESTER.ARPA -42 -41542 SU-AIMVAX.ARPA -50 -49575 UCI-CIP4.ARPA -57 -57060 SU-SAFE.ARPA -59 -59212 SU-PSYCH.ARPA -59 -58421 UDEL-MICRO.ARPA 62 63214 UIUCDCSB.ARPA 63 63865 BELLCORE-CS-GW.ARPA 71 71402 USGS2-MULTICS.ARPA 76 77018 BBNG.ARPA 81 81439 UDEL-DEWEY.ARPA 89 89283 UCI-CIP3.ARPA -102 -102148 UIUC.ARPA 105 105843 UCI-CIP2.ARPA -185 -185250 UCI-CIP.ARPA -576 -576386 OSLO-VAX.ARPA 3738 3739395 Mills [Page 25] RFC 956 September 1985 Algorithms for Synchronizing Network Clocks DEVVAX.TN.CORNELL.EDU 3657 3657026 PATCH.ARPA -86380 20411 IPTO-FAX.ARPA -86402 -1693 NETWOLF.ARPA 10651435 -62164450 Table A8. Comparison of UDP and ICMP Host Clock Offsets Allowing for various degrees of truncation and roundoff abuse in the various implementations, discrepancies of up to a second could be expected between UDP and ICMP time. While the results for most hosts confirm this, some discrepancies are far greater, which may indicate defective implementations, excessive swapping delays and so forth. For instance, the ICMP time indicated by UCI-CIP5.ARPA is almost 2.5 seconds less than the UDP time. Even though the UDP and ICMP times indicated by OSLO-VAX.ARPA and DEVVAX.TN.CORNELL.EDU agree within nominals, the fact that they are within a couple of minutes or so of exactly one hour early (3600 seconds) lends weight to the conclusion they were incorrectly set, probably by an operator who confused local summer and standard time. Something is clearly broken in the case of PATCH.ARPA, IPTO-FAX.ARPA and NETWOLF.ARPA. Investigation of the PATCH.ARPA and IPTO-FAX.ARPA reveals that these hosts were set by hand accidently one day late (-86400 seconds), but otherwise close to the correct time-of-day. Since the ICMP time rolls over at 2400 UT, the ICMP offset was within nominals. No explanation is available for the obviously defective UDP and ICMP times indicated by NETWOLF.ARPA, although it was operating within nominals at least in the first experiment. Mills [Page 26]